// https://leetcode.cn/problems/maximum-sum-circular-subarray/description/

// 算法思路总结：
// 1. 环形数组最大子数组和问题
// 2. 同时计算最大子数组和和最小子数组和
// 3. 两种情况比较：正常区间 vs 环形区间（总和-最小和）
// 4. 特殊情况：全负数时直接返回最大子数组和
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <numeric>

class Solution 
{
public:
    int maxSubarraySumCircular(vector<int>& nums) 
    {
        const int INF = 0x3f3f3f3f;
        int m = nums.size();

        vector<int> f(m + 1, 0), g(m + 1, 0);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int maxVal = -INF, minVal = INF;
        for (int i = 1 ; i <= m ; i++)
        {
            f[i] = max(f[i - 1] + nums[i - 1], nums[i - 1]);
            g[i] = min(g[i - 1] + nums[i - 1], nums[i - 1]);
            maxVal = max(maxVal, f[i]);
            minVal = min(minVal, g[i]);
        }
        return sum == minVal ? maxVal : max(maxVal, sum - minVal);
    }
};

int main()
{
    vector<int> v1 = {1,-2,3,-2}, v2 = {5,-3,5};
    Solution sol;

    cout << sol.maxSubarraySumCircular(v1) << endl;
    cout << sol.maxSubarraySumCircular(v2) << endl;

    return 0;
}